// 437.路径总和3
package LeetcodeHot100;

import java.util.HashMap;
import java.util.Map;


public class Solution437 {
    public int pathSum(TreeNode root, int targetSum) {
        // <值，出现的次数>
        Map<Long, Integer> map = new HashMap<>();
        map.put(0l, 1);
        return dfs(root, map, 0l, targetSum);
    }

    public int dfs(TreeNode root, Map<Long, Integer> map, long currentValue, int targetSum) {
        if (root == null)
            return 0;
        int result = 0;
        // 计算前缀和
        currentValue += root.val;
        result += map.getOrDefault(currentValue - targetSum, 0);
        map.put(currentValue, map.getOrDefault(currentValue, 0) + 1);
        result += dfs(root.left, map, currentValue, targetSum);
        result += dfs(root.right, map, currentValue, targetSum);
        map.put(currentValue, map.getOrDefault(currentValue, 0) - 1);
        return result;
    }
}
